Recently, as mobile phones and the Internet have been widely used, the amount of data to be handled is increased. As such, it is required to process a large amount of data at a higher speed. In such a situation, as a system for storing a large amount of data, a demand for a key value store (KVS) is increasing. In a key value store, data (value) is associated with a unique sign (key), and they are stored in a pair. Hereinafter, data in which a key and a value are paired is called KV data. In particular, a system having a function in which units of KV data are stored distributedly in a plurality of servers, storage devices, and the like is called a distributed KVS. A distributed KVS focuses on scalability and throughput. As such, it has been unsuitable for a system requiring data consistency and a system involving transaction processing. However, due to needs for analysis and transaction processing of a larger amount of data, it is required to perform high-speed processing on a larger amount of data, while keeping data consistency, even in a distributed KVS.
As techniques for improving data processing capability, use of a cache and a simultaneous execution control method for transactions have been known. Use of a cache is a technique of storing frequently used data in a high-speed storage device to thereby realize high-speed processing by eliminating wasteful processing of reading it every time from a low-speed persistent storage device. On the other hand, a simultaneous execution control method for transactions is a technique of executing, in parallel, a plurality of transactions of updating the same information, while keeping data consistency.
It has been known that simultaneous execution control methods for transactions include a method based on pessimistic exclusion and a method based on optimistic exclusion. In a simultaneous execution control method based on pessimistic exclusion, before execution of a transaction, every data to be referred to or updated in such a transaction is excluded (locked) in advance to thereby secure the data consistency. However, in simultaneous execution control based on pessimistic exclusion, as processing of another server using the same data cannot be performed until processing by the server executing the processing obtaining exclusion, which lacks scalability. As such, in a distributed key value store focusing on scalability, a simultaneous execution control method based on optimistic exclusion is used